package doublelink;

public class DoubleLinkedList {
    // 当前链表中有效的元素个数
    private int size;
    // 头节点
    private Node head;
    // 尾节点
    private Node tail;

    //头插
    public void addFirst(int val) {
        Node node = new Node(null,val,head);
//        判断链表是否为空
        if (head == null) {
            tail = node;
        }else {
//            链表不为空时
            head.prev = node;
        }
        head = node;
        size ++;
    }

//    尾插
    public void addLast(int val) {
        Node node = new Node(tail,val,null);
//        当链表为空时
        if (tail == null) {
            head = node;
        }else {
            tail.next = node;
        }
        tail = node;
        size ++;
    }

//    在链表中间插入元素
    public void addIndex(int index,int val) {
//        判断index的合法性
        if (index < 0 || index > size) {
            System.out.println("add index illegal!");
            return;
        }else if (index == 0) {
            addFirst(val);
        }else if (index == size) {
            addLast(val);
        }else {
//            在中间插入，找到index前驱
            Node prev = node(index - 1);
            Node node = new Node(prev,val,prev.next);
            prev.next.prev = node;
            prev.next = node;
            size ++;
        }
    }


//    删除节点
//    分治思想
    public void unlink(Node node) {
        Node prev = node.prev;
        Node next = node.next;
//        处理前半段
        if (prev == null) {
            head = next;
        }else {
            prev.next = next;
            node.next = null;
        }
//        处理后半段
        if (next == null) {
            tail = prev;
        }else {
            next.prev = prev;
            node.next = null;
        }
        size --;
    }


//    删除指定节点
    public void removeIndex(int index) {
//        判断index的合法性
        if (index < 0 || index >= size) {
            System.out.println("remove index illegal!");
            return;
        }else {
//            找到指定节点
            Node node = node(index);
//            删除该节点
            unlink(node);
        }
    }
//    头删
    public void removeFirst() {
        removeIndex(0);
    }
//    尾删
    public void removeLast() {
        removeIndex(size - 1);
    }
//    删除重复节点一次
    public void removeValOnce(int val) {
//        找到指定节点
        for (Node cur = head;cur != null;cur = cur.next) {
            if (cur.val == val) {
                unlink(cur);
                break;
            }
        }
    }
//    删除所有重复节点
    public void removeValAll(int val) {
        for (Node cur = head;cur != null;) {
            if (cur.val == val){
//                将x后的节点暂存
                Node next = cur.next;
                unlink(cur);
                cur = next;
            }else {
                cur = cur.next;
            }
        }
    }


//    找到对应节点
    private Node node(int index) {
        Node ret = null;
        if (index < (size >> 1)) {
            ret = head;
            for (int i = 0; i < index; i++) {
                ret = ret.next;
            }
        }else {
            ret = tail;
            for (int i = size - 1; i < index; i--) {
                ret = ret.next;
            }
        }
        return ret;
    }


    //打印链表
    public String toString() {
        String ret = " ";
        Node node = head;
        while (node != null) {
            ret += node.val + "->";
            node = node.next;
        }
        ret += "NULL";
        return ret;
    }
}








/**
 * 双链表的节点类
 */
class Node {
    // 指向前驱节点
    Node prev;
    // 保存具体值
    int val;
    // 指向后继节点
    Node next;

    public Node(int val) {
        this.val = val;
    }

    public Node(Node prev, int val, Node next) {
        this.prev = prev;
        this.val = val;
        this.next = next;
    }
}